Có bằng chứng về việc người hiện đại cư trú tại Malaysia cách nay 40.000 năm.[10] Tại bán đảo Mã Lai, các cư dân đầu tiên được cho là người Negrito.[11] Các thương nhân và người định cư từ Ấn Độ và Trung Quốc đến từ thế kỷ I CN, lập nên các thương cảng và đô thị duyên hải vào thế kỷ II và III. Sự xuất hiện của họ khiến ảnh hưởng của Ấn Độ và Trung Quốc có tác động mạnh đối các văn hóa bản địa, và người dân trên bán đảo Mã Lai tiếp nhận Ấn Độ giáo và Phật giáo. Các bản khắc bằng tiếng Phạn xuất hiện từ thế kỷ IV hoặc V.[12] Vương quốc Langkasuka nổi lên vào khoảng thế kỷ II ở khu vực bắc bộ của bán đảo Mã Lai, tồn tại cho đến khoảng thế kỷ XV.[13] Từ thế kỷ VII đến thế kỷ XIII, phần lớn nam bộ bán đảo Mã Lai là một phần của đế quốc hàng hải Srivijaya. Sau khi Srivijaya sụp đổ, đế quốc Majapahit có ảnh hưởng đối với hầu hết Malaysia bán đảo và quần đảo Mã Lai.[14] Hồi giáo bắt đầu truyền bá trong cộng đồng người Mã Lai vào thế kỷ XIV.[15] Vào đầu thế kỷ XV, một hậu duệ của hoàng thất Srivijaya là Parameswara thành lập Vương quốc Malacca, đây thường được xem là quốc gia độc lập đầu tiên tại bán đảo Mã Lai.[16] Đương thời, Malacca là một trung tâm thương mại quan trọng.

Năm 1511, Bồ Đào Nha chinh phục Malacca,[15] đến năm 1641 thì lãnh thổ này bị người Hà Lan chiếm đoạt. Năm 1786, Đế quốc Anh thiết lập một sự hiện diện tại Malaya, khi đó Sultan của Kedah cho Công ty Đông Ấn Anh thuê Penang. Người Anh giành được Singapore vào năm 1819,[17] và đến năm 1824 thì đoạt quyền kiểm soát Malacca sau Hiệp định Anh-Hà Lan. Năm 1826, người Anh bắt đầu quản lý trực tiếp Penang, Malacca, Singapore, và đảo Labuan. Đến thế kỷ XX, tại các quốc gia Pahang, Selangor, Perak, và Negeri Sembilan, được gọi chung là Các quốc gia Mã Lai liên minh, có các thống sứ người Anh được bổ nhiệm để cố vấn cho các quân chủ Mã Lai theo điều khoản trong các hiệp định mà họ từng ký.[18] Năm quốc gia còn lại trên bán đảo được gọi là Các quốc gia Mã Lai phi liên minh, các quốc gia này không chịu sự quản lý trực tiếp của người Anh, song cũng chấp thuận các cố vấn người Anh. Tiến triển tại Bán đảo và Borneo nhìn chung là tách biệt cho đến thế kỷ XIX. Trong thời gian người Anh cai trị, họ khuyến khích người Hoa và người Ấn nhập cư để trở thành lao công.[19] Khu vực mà nay là Sabah nằm dưới sự cai trị của người Anh với tên gọi Bắc Borneo khi cả Sultan của Brunei và Sultan của Sulu chuyển giao quyền sở hữu các lãnh thổ của riêng họ từ năm 1877 đến năm 1878.[20] Năm 1842, Sultan của Brunei nhượng Sarawak cho James Brooke, các Rajah da trắng kế tập cai trị Vương quốc Sarawak độc lập cho đến khi lãnh thổ này trở thành một thuộc địa vương thất Anh vào năm 1946.[21]

Trong Chiến tranh thế giới thứ hai, quân đội Nhật Bản tấn công, đánh bại quân Anh và chiếm đóng Malaya, Bắc Borneo, Sarawak, và Singapore trong ba năm. Trong thời kỳ này, căng thẳng sắc tộc gia tăng và chủ nghĩa dân tộc phát triển.[22] Sự ủng hộ của dân chúng đối với độc lập tăng lên sau khi lực lượng Đồng Minh tái chiếm Malaya.[23]

Hậu chiến, người Anh tiến hành các nỗ lực nhằm hợp nhất việc cai quản Malaya trong một thuộc địa vương thất duy nhất gọi là Liên hiệp Malaya (Malayan Union), tuy nhiên điều này bị người Mã Lai phản đối mạnh, người Mã Lai phản đối việc địa vị của các quân chủ Mã Lai suy yếu và việc trao quyền công dân cho người gốc Hoa. Liên hiệp Malaya được thành lập vào năm 1946 và bao gồm toàn bộ các thuộc địa của Anh Quốc tại khu vực bán đảo Mã Lai, ngoại trừ Singapore, song chính thể này nhanh chóng bị giải thể và thay thế bởi Liên bang Malaya (Federation of Malaya), chính thể này khôi phục quyền tự trị cho các quân chủ của các quốc gia Mã Lai dưới sự bảo hộ của người Anh.[24] Trong thời kỳ này, dưới sự lãnh đạo của Đảng Cộng sản Malaya, quân nổi dậy mà hầu hết là người gốc Hoa tiến hành các hoạt động du kích với mục đích đánh đuổi người Anh ra khỏi Malaya. Tình trạng khẩn cấp Malaya kéo dài từ năm 1948 đến năm 1960, và liên quan đến một chiến dịch chống nổi loạn kéo dài của quân Thịnh vương chung tại Malaya.[25] Sau đó, người ta đưa ra một kế hoạch nhằm Liên hiệp Malaya với các thuộc địa vương thất Bắc Borneo (gia nhập với tên Sabah), Sarawak, và Singapore. Ngày đề xuất hợp thành liên bang là 31 tháng 8 năm 1963, tuy nhiên, thời điểm bị trì hoãn cho đến ngày 16 tháng 9 năm 1963 do phản đối của Indonesia dưới quyền Tổng thống Sukarno và Đảng Nhân dân Liên hiệp Sarawak.[26]

Sự thành lập liên bang khiến các căng thẳng tăng cao, bao gồm một cuộc xung đột với Indonesia, Singapore bị trục xuất vào năm 1965,[27][28] và xung đột sắc tộc. Xung đột sắc tộc lên đến đỉnh điểm trong các cuộc bạo loạn sắc tộc ngày 13 tháng 5 năm 1969.[29] Sau các cuộc bạo loạn, Thủ tướng Tun Abdul Razak đưa ra Chính sách Kinh tế mới gây tranh cãi, mục đích là nhằm nâng cao phần sở hữu kinh tế của bumiputera.[30] Dưới thời Thủ tướng Mahathir Mohamad, Malaysia trải qua tăng trưởng kinh tế và đô thị hóa nhanh chóng. Kinh tế Malaysia chuyển đổi từ dựa vào nông nghiệp sang dựa vào chế tạo và công nghiệp. Nhiều siêu dự án được hoàn thành, chẳng hạn như tháp đôi Petronas, xa lộ Nam-Bắc, hành lang đa phương tiện siêu cấp, và thủ đô hành chính liên bang mới Putrajaya.[31] Tuy nhiên, vào cuối thập niên 1990, Khủng hoảng tài chính châu Á suýt khiến cho đồng Ringgit cùng các thị trường chứng khoán và bất động sản Malaysia sụp đổ.[32]